package com.example.demo.leetcode.top100;

import java.util.Stack;

/**
 * ******************************************************
 *
 * @author liugh9
 * @version 1.0
 * @classname _7接雨水
 * @description
 * @date 2023/06/03 22:58
 * <p>
 * ******************************************************
 */
public class _7接雨水 {

    /**
     * 对于任意一个位置 i，能够装的水为：
     * <p>
     * water[i] = min(
     * # 左边最高的柱子
     * max(height[0..i]),
     * # 右边最高的柱子
     * max(height[i..end])
     * ) - height[i]
     *
     * @param height
     * @return
     */
    public int trap(int[] height) {
        if (height.length == 0) {
            return 0;
        }
        int n = height.length;
        int res = 0;
        // 数组充当备忘录
        int[] l_max = new int[n];
        int[] r_max = new int[n];
        // 初始化 base case
        l_max[0] = height[0];
        r_max[n - 1] = height[n - 1];
        // 从左向右计算 l_max
        for (int i = 1; i < n; i++) {
            l_max[i] = Math.max(height[i], l_max[i - 1]);
        }
        // 从右向左计算 r_max
        for (int i = n - 2; i >= 0; i--) {
            r_max[i] = Math.max(height[i], r_max[i + 1]);
        }

        for (int i = 0; i < n; i++) {
            res += Math.min(l_max[i], r_max[i]) - height[i];
        }
        return res;
    }
}
